Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 11 На тему: «Методи пошуку. Алгоритм Кнута-Моріса-Прата» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: Семчишин Ю. Б. Коротєєва Т. О. Вовчак І. Г. Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами пошуку. Алгоритм Кнута-Моріса-Прата. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із алгоритмом Кнута-Моріса-Прата. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема алгоритму Кнута-Моріса-Прата. ТЕОРЕТИЧНІ ВІДОМОСТІ Алгоритм Кнута-Моріса-Прата (англ. Knuth–Morris–Pratt algorithm) шукає входження слова W у рядку S використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації, для того щоб визначити, де наступне входження може початися, таким чином пропускаючи кілька разову перевірка попередньо порівняних символів. Алгоритм був винайдений вченими Donald Knuth та Vaughan Pratt і незалежно J. H. Morris у 1977 році, але був опублікований у спільній статті. Маємо масив символів S з n елементів (текст) та масив P з m - взірець. Необхідно знайти перше входження взірця в масив. Схема алгоритму полягає у поступовому порівнянні взірця з текстом та зсуву по тексту на кількість співпавших символів у разі знайденого неспівпадіння. Алгоритм КМП КМП1. Встановити і=0. КМП2. j=0, d=1. КМП2. Поки j<m, i<n КМП 3. Перевірка: якщо s[i]=p[j], то d++, i++.j++ поки d != m. Інакше встановити зсув взірця на d позицій по тексту. Перейти на крок КМП2. КМП4. Кінець. Складність алгоритму становить O(n+m). Приклад, Hoola-Hoola girls like Hooligan - текст Hooligan – взірець Hoola-Hoola girls like Hooligan Hooligan i!=a, d=4 Hooligan H!=a, d=1 Hooligan H!=-, d=1 Hooligan i!=a, d=4 ….. Hooligan d=m=8 РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://www.wikipedia.org/. Donald Ervin Knuth «The Art of Computer Programming». 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм Кнута-Моріса-Прата. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи пошуку? Який метод пошуку був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість пошуку? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами пошуку вам відомими. Наскільки являється ефективним даний метод пошуку? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?